#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=77 lang=cpp
 *
 * [77] 组合
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res; vector<int> temp;
        vector<bool> used(n + 1, false);
        dfs(temp, 1, k, n, res);
        return res;
    }

    void dfs(vector<int> & now, int index, int k, int n, vector<vector<int>> & res) {
        if (now.size() == k) {
            res.push_back(now);
            return;
        }
        if (index == n + 1) return;
        now.push_back(index);
        dfs(now, index + 1, k, n, res);
        now.pop_back();
        dfs(now, index + 1, k, n, res);
    }
};
// @lc code=end

